package com.kehao.leetcode.jzoffer;

import java.util.List;

/**
 * @author Kehao.Chen
 * @version 1.0
 * @date 2022/6/23 16:57
 */
public class JZSolution026 {

    private static class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    private ListNode reverseList(ListNode head) {
        if(head==null) return null;
        ListNode h = new ListNode();
        ListNode p = head;
        ListNode p1 = p.next;
        while (p!=null){
            p.next = h.next;
            h.next = p;
            p = p1;
            p1 = p1==null?p1:p1.next;
        }
        return h.next;
    }

    public void reorderList(ListNode head) {
        ListNode h = new ListNode();
        ListNode pre = new ListNode();
        ListNode slow = head;
        pre.next = slow;
        ListNode fast = head;

        while (true){
            try {
                slow = slow.next;
                pre = pre.next;
                fast = fast.next.next;
            }catch (NullPointerException e){
                break;
            }
        }
        pre.next = null;
        ListNode big = reverseList(slow);
        ListNode small = head;
        ListNode p = h;
        int i =0;
        while (big!=null&&small!=null){
            if(i%2==0){
                p.next = small;
                p = p.next;
                small = small.next;
            }else {
                p.next = big;
                p = p.next;
                big = big.next;
            }
            i++;
        }
        if (big!=null){
            p.next = big;
        }
        if(small!=null){
            p.next = small;
        }
    }
}
